package CH02链表结构.LeetCode链表;

public class LC86 {
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode small = null;
        ListNode p1 = null;
        ListNode big = null;
        ListNode p2 = null;
        ListNode p = head;
        while (p != null) {
            if (p.val < x) {
                if (small == null) {
                    small = p;
                    p1 = p;
                } else {
                    p1.next = p;
                    p1 = p1.next;
                }
            } else {
                if (big == null) {
                    big = p;
                    p2 = p;
                } else {
                    p2.next = p;
                    p2 = p2.next;
                }
            }
            p = p.next;
        }
        if (p1 == null || p2 == null) {
            return head;
        }
        p1.next = null;
        p2.next = null;
        p1.next = big;
        return small;
    }
}